package com.datastructure.test.threeoftotal;

import java.util.ArrayList;
import java.util.Arrays;

public class ThreeOfTotal {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();

        if(num==null || num.length<3){
            return res;
        }
        Arrays.sort(num);// 排序
        for(int i=0;i<num.length-2;i++){
            if(num[i]>0){
                break;// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            }
            if(i>0 && num[i]==num[i-1]){
                continue;// 去重
            }
            int L=i+1;
            int R=num.length-1;

            while(L<R){
                int sum=num[i]+num[L]+num[R];
                if(sum==0){
                    ArrayList<Integer> list=new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[L]);
                    list.add(num[R]);
                    res.add(list);

                    while(L<R && num[L]==num[L+1]){
                        L++;
                    }
                    while(L<R && num[R]==num[R-1]){
                        R--;
                    }
                    //不等于的时候再加1
                    L++;
                    R--;
                }
                else if(sum>0){
                    R--;
                }
                else {
                    L++;
                }
            }
        }
        return res;
    }
}
